#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
#define N 2010
    int ispalin[N][N] = { 0 };
    vector<int> dp = vector<int>(N, INT_MAX);

    bool checkPalin(const string& s, int left, int right)
    {
        if (ispalin[left][right])
            return ispalin[left][right] == 1 ? false : true;
        if (left >= right)
            return true;
        if (s[left] != s[right])
        {
            ispalin[left][right] = 1;
            return false;
        }
        bool flag = checkPalin(s, left + 1, right - 1);
        ispalin[left][right] = flag + 1;
        return flag;
    }

    int dfs(const string& s, int end)
    {
        if (dp[end] != INT_MAX)
            return dp[end];
        for (int start = end; start >= 0; start--)
        {
            if (checkPalin(s, start, end))
            {
                if (start == 0)
                {
                    dp[end] = 0;
                    return dp[end];
                }
                int times = dfs(s, start - 1) + 1;
                dp[end] = min(dp[end], times);
            }
        }
        return dp[end];
    }

    int minCut(string s) {
        int n = s.size();
        for (int i = 0; i < n; i++)
            dfs(s, i);
        return dp[n - 1];
    }
};